#include <bits/stdc++.h>
using namespace std;

/*
3249. 统计好节点的数目
已解答
中等
相关标签
相关企业
提示
现有一棵 无向 树，树中包含 n 个节点，按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。

如果一个节点的所有子节点为根的 子树 包含的节点数相同，则认为该节点是一个 好节点。

返回给定树中 好节点 的数量。

子树 指的是一个节点以及它所有后代节点构成的一棵树。

 

 

示例 1：

输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]

输出：7

说明：


树的所有节点都是好节点。

示例 2：

输入：edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]

输出：6

说明：


树中有 6 个好节点。上图中已将这些节点着色。

示例 3：

输入：edges = [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]

输出：12

解释：


除了节点 9 以外其他所有节点都是好节点。

 

提示：

2 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
输入确保 edges 总表示一棵有效的树
*/

// 法一
class Solution {
	public:
	int countGoodNodes(vector<vector<int>>& edges) {
		// 构建树的邻接表表示
		// DFS遍历树，计算每个节点的子树节点数
		// 判断
		int n = edges.size() + 1;
		vector<vector<int>> adj(n);
		int is_goodCount = 0;
		// 邻接表
		for (auto& edge : edges) {
			adj[edge[0]].push_back(edge[1]);
			adj[edge[1]].push_back(edge[0]);
		}
		
		// DFS
		function<int(int, int)> dfs = [&](int node, int parent) -> int {
			int total_size = 1, sub_size = -1;
			bool is_goodNode = true;
			for (int child : adj[node]) {
				if(child == parent)     continue;
				int child_size = dfs(child, node);
				total_size += child_size;
				if(sub_size == -1)  sub_size = child_size;
				else if(child_size != sub_size)     is_goodNode = false;
			}
			if(is_goodNode) is_goodCount++;
			return total_size;
		};

		// 计算然后检查
		dfs(0, -1);
		
		return is_goodCount;
	}
};

// 法二
class Solution {
	public:
	// 静态数组大小常量（根据题目约束n<=1e5设定）
	static const int MAX_NODES = 1e5 + 10;

	// 邻接表三数组（更清晰的命名）
	int adjacency_head[MAX_NODES];       // 原h数组
	int edge_destination[MAX_NODES * 2]; // 原e数组（存储边的终点）
	int next_edge_index[MAX_NODES * 2];  // 原ne数组（链表指针）
	int edge_count = 0;                  // 原idx（当前边索引）

	int good_node_count = 0; // 原res（结果计数器）
	bool visited[MAX_NODES]; // 原st（访问标记数组）

	// 添加双向边（更明确的函数名）
	void add_edge(int from_node, int to_node) {
		edge_destination[edge_count] = to_node;
		next_edge_index[edge_count] = adjacency_head[from_node];
		adjacency_head[from_node] = edge_count++;
	}

	int countGoodNodes(vector<vector<int>>& edges) {
		good_node_count = 0;
		edge_count = 0;
		memset(adjacency_head, -1, sizeof adjacency_head);

		// 构建邻接表
		for (auto& edge : edges) {
			add_edge(edge[0], edge[1]);
			add_edge(edge[1], edge[0]);
		}

		memset(visited, 0, sizeof visited);
		depthFirstSearch(0); // 原dfs(0)
		return good_node_count;
	}

	// DFS遍历返回子树节点数（更明确的参数名）
	int depthFirstSearch(int current_node) {
		visited[current_node] = true;
		int subtree_size = 1;      // 原sum（子树总节点数）
		int first_child_size = -1; // 原single_cnt（首个子树大小）
		bool is_valid_node = true; // 原flag（有效性标记）

		// 遍历邻接链表
		for (int edge_ptr = adjacency_head[current_node]; edge_ptr != -1;
			 edge_ptr = next_edge_index[edge_ptr]) {

			int neighbor_node = edge_destination[edge_ptr]; // 原j
			if (visited[neighbor_node])
				continue;

			visited[neighbor_node] = true;
			int child_subtree_size = depthFirstSearch(neighbor_node); // 原k

			subtree_size += child_subtree_size;

			// 比较子树大小是否一致
			if (first_child_size == -1) {
				first_child_size = child_subtree_size;
			} else if (child_subtree_size != first_child_size) {
				is_valid_node = false; // 发现不一致子树
			}
		}

		// 满足条件时计数（包含无子节点的叶子情况）
		if (is_valid_node)
			good_node_count++;
		return subtree_size;
	}
};